home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format CD 42 / Amiga Format AFCD42 (Issue 126, Aug 1999).iso / -serious- / programming / other / jikes / src / unzip.h < prev    next >
C/C++ Source or Header  |  1999-05-14  |  17KB  |  374 lines
  1. // $Id: unzip.h,v 1.2 1999/01/13 21:48:42 shields Exp $
  2. #ifndef unzip_INCLUDED
  3. #define unzip_INCLUDED
  4.  
  5. #include "config.h"
  6.  
  7. //
  8. // NOTE: Jikes incorporates compression code from the Info-ZIP
  9. // group. There are no extra charges or costs due to the use of
  10. // this code, and the original compression sources are freely
  11. // available from http://www.cdrom/com/pub/infozip/ or 
  12. // ftp://ftp.cdrom.com/pub/infozip/ on the Internet.
  13. // The sole use by Jikes of this compression code is contained in the 
  14. // files unzip.h and unzip.cpp, which are based on Info-ZIP's inflate.c and 
  15. // associated header files.
  16. //
  17.  
  18. //
  19. // You can do whatever you like with this source file, though I would
  20. // prefer that if you modify it and redistribute it that you include
  21. // comments to that effect with your name and the date.  Thank you.
  22. // The abbreviated History list below includes the work of the
  23. // following:
  24. // M. Adler, G. Roelofs, J-l. Failly, J. Bush, C. Ghisler, A. Verheijen,
  25. // P. Kienitz, C. Spieler, S. Maxwell, J. Altman
  26. // Only the first and last entries from the original inflate.c are
  27. // reproduced here.
  28. //
  29.  
  30. //
  31. // History:
  32. // vers    date          who           what
  33. // ----  ---------  --------------  ------------------------------------
  34. //  a    ~~ Feb 92  M. Adler        used full (large, one-step) lookup table
  35. //  ...
  36. //  c16  20 Apr 97  J. Altman       added memzero(v[]) in huft_build()
  37. //
  38.  
  39. #define DFUNZIP /* needed for unzip compilation*/
  40. #include <stdio.h>
  41. #include <stdlib.h>
  42. #include <string.h>
  43.  
  44. //
  45. // inflate.c -- put in the public domain by Mark Adler
  46. // version c15c, 28 March 1997
  47. //
  48.  
  49. //
  50. // Inflate deflated (PKZIP's method 8 compressed) data.  The compression
  51. // method searches for as much of the current string of bytes (up to a
  52. // length of 258) in the previous 32K bytes.  If it doesn't find any
  53. // matches (of at least length 3), it codes the next byte.  Otherwise, it
  54. // codes the length of the matched string and its distance backwards from
  55. // the current position.  There is a single Huffman code that codes both
  56. // single bytes (called "literals") and match lengths.  A second Huffman
  57. // code codes the distance information, which follows a length code.  Each
  58. // length or distance code actually represents a base value and a number
  59. // of "extra" (sometimes zero) bits to get to add to the base value.  At
  60. // the end of each deflated block is a special end-of-block (EOB) literal/
  61. // length code.  The decoding process is basically: get a literal/length
  62. // code; if EOB then done; if a literal, emit the decoded byte; if a
  63. // length then get the distance and emit the referred-to bytes from the
  64. // sliding window of previously emitted data.
  65.  
  66. // There are (currently) three kinds of inflate blocks: stored, fixed, and
  67. // dynamic.  The compressor outputs a chunk of data at a time and decides
  68. // which method to use on a chunk-by-chunk basis.  A chunk might typically
  69. // be 32K to 64K, uncompressed.  If the chunk is uncompressible, then the
  70. // "stored" method is used.  In this case, the bytes are simply stored as
  71. // is, eight bits per byte, with none of the above coding.  The bytes are
  72. // preceded by a count, since there is no longer an EOB code.
  73.  
  74. // If the data are compressible, then either the fixed or dynamic methods
  75. // are used.  In the dynamic method, the compressed data are preceded by
  76. // an encoding of the literal/length and distance Huffman codes that are
  77. // to be used to decode this block.  The representation is itself Huffman
  78. // coded, and so is preceded by a description of that code.  These code
  79. // descriptions take up a little space, and so for small blocks, there is
  80. // a predefined set of codes, called the fixed codes.  The fixed method is
  81. // used if the block ends up smaller that way (usually for quite small
  82. // chunks); otherwise the dynamic method is used.  In the latter case, the
  83. // codes are customized to the probabilities in the current block and so
  84. // can code it much better than the pre-determined fixed codes can.
  85.  
  86. // The Huffman codes themselves are decoded using a multi-level table
  87. // lookup, in order to maximize the speed of decoding plus the speed of
  88. // building the decoding tables.  See the comments below that precede the
  89. // lbits and dbits tuning parameters.
  90.  
  91. // GRR:  return values(?)
  92. //         0  OK
  93. //         1  incomplete table
  94. //         2  bad input
  95. //         3  not enough memory
  96. //
  97.  
  98. //
  99. // If BMAX needs to be larger than 16, then h and x[] should be unsigned long.
  100. //
  101. #define BMAX 16         /* maximum bit length of any code (16 for explode) */
  102. #define N_MAX 288       /* maximum number of codes in any set */
  103.  
  104.  
  105. //
  106. // Notes beyond the 1.93a appnote.txt:
  107.  
  108. // 1. Distance pointers never point before the beginning of the output
  109. //    stream.
  110. // 2. Distance pointers can point back across blocks, up to 32k away.
  111. // 3. There is an implied maximum of 7 bits for the bit length table and
  112. //    15 bits for the actual data.
  113. // 4. If only one code exists, then it is encoded using one bit.  (Zero
  114. //    would be more efficient, but perhaps a little confusing.)  If two
  115. //    codes exist, they are coded using one bit each (0 and 1).
  116. // 5. There is no way of sending zero distance codes--a dummy must be
  117. //    sent if there are none.  (History: a pre 2.0 version of PKZIP would
  118. //    store blocks with no distance codes, but this was discovered to be
  119. //    too harsh a criterion.)  Valid only for 1.93a.  2.04c does allow
  120. //    zero distance codes, which is sent as one code of zero bits in
  121. //    length.
  122. // 6. There are up to 286 literal/length codes.  Code 256 represents the
  123. //    end-of-block.  Note however that the static length tree defines
  124. //    288 codes just to fill out the Huffman codes.  Codes 286 and 287
  125. //    cannot be used though, since there is no length base or extra bits
  126. //    defined for them.  Similarily, there are up to 30 distance codes.
  127. //    However, static trees define 32 codes (all 5 bits) to fill out the
  128. //    Huffman codes, but the last two had better not show up in the data.
  129. // 7. Unzip can check dynamic Huffman blocks for complete code sets.
  130. //    The exception is that a single code would not be complete (see #4).
  131. // 8. The five bits following the block type is really the number of
  132. //    literal codes sent minus 257.
  133. // 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
  134. //    (1+6+6).  Therefore, to output three times the length, you output
  135. //    three codes (1+1+1), whereas to output four times the same length,
  136. //    you only need two codes (1+3).  Hmm.
  137. //10. In the tree reconstruction algorithm, Code = Code + Increment
  138. //    only if BitLength(i) is not zero.  (Pretty obvious.)
  139. //11. Correction: 4 Bits: # of Bit Length codes - 4     (4 - 19)
  140. //12. Note: length code 284 can represent 227-258, but length code 285
  141. //    really is 258.  The last length deserves its own, short code
  142. //    since it gets used a lot in very redundant files.  The length
  143. //    258 is special since 258 - 3 (the min match length) is 255.
  144. //13. The literal/length and distance code bit lengths are read as a
  145. //    single stream of lengths.  It is possible (and advantageous) for
  146. //    a repeat code (16, 17, or 18) to go across the boundary between
  147. //    the two sets of lengths.
  148. //
  149.  
  150. #define PKZIP_BUG_WORKAROUND    /* PKZIP 1.93a problem--live with it */
  151.  
  152. //
  153. //  inflate.h must supply the unsigned char slide[WSIZE] array, the zvoid typedef
  154. //  (void if (void *) is accepted, else char) and the NEXTBYTE,
  155. //  FLUSH() and memzero macros.  If the window size is not 32K, it
  156. //  should also define WSIZE.  If INFMOD is defined, it can include
  157. //  compiled functions to support the NEXTBYTE and/or FLUSH() macros.
  158. //  There are defaults for NEXTBYTE and FLUSH() below for use as
  159. //  examples of what those functions need to do.  Normally, you would
  160. //  also want FLUSH() to compute a crc on the data.  
  161.  
  162. //  This module uses the external functions malloc() and free() (and
  163. //  probably memset() or bzero() in the memzero() macro).  Their
  164. //  prototypes are normally found in <string.h> and <stdlib.h>.
  165. //
  166.  
  167. /* #define DEBUG */
  168.  
  169.  
  170. #ifndef WSIZE           /* default is 32K */
  171. #  define WSIZE 0x8000  /* window size--must be a power of two, and at least */
  172. #endif